Peer-to-peer (P2P) systems employ a network which connects participating machines having equal or similar capabilities and responsibilities. These systems perform tasks without the coordination of a conventional server (or with minimal set-up coordination by a server). For instance, FIG. 1 shows a high-level depiction of a P2P system 100. The system 100 includes a collection of peer entities (102-112) having equal or similar capabilities and responsibilities. In one example, the peer entities (102-112) may correspond to independent personal computer devices coupled together via an Internet or intranet. The peer entities (102-112) can directly transfer files or other information between themselves (as indicated by exemplary communication path 114) without the aid of a server. A general introduction to P2P systems can be found in D. S. Milojicic, V. Kalogeraki, R. Lukose, K. Nagaraja, J. Pruyne, B. Richard, S. Rollins, and Z. Xu., “Peer-To-Peer Computing,” Technical Report HPL-2002-57, HP Lab, 2002.
P2P systems commonly use a distributed hash table (DHT) to facilitate the storage and retrieval of objects from peer entities participating in the systems. As the name suggests, a distributed hash table (DHT) refers to a hash table that is distributed over plural locations, such as distributed over plural stores associated with different computer devices. A distributed hash table specifies a plurality of DHT nodes having respective assigned IDs. The DHT nodes collectively define an abstract DHT logical space. An object can be inserted into or retrieved from this DHT logical space by subjecting this object to a hashing function to produce a key. This key is then used to locate a particular target node ID in the DHT logical space that will receive the object or from which the object can be retrieved. That is, each DHT node is associated with a range of keys; an object is added to or retrieved from a particular DHT node depending on whether the object's key falls within the range of keys associated with that particular DHT node. Unlike non-distributed hash table implementations, DHT nodes can freely join and leave the DHT logical space (e.g., corresponding to computer devices joining and leaving the P2P system, respectively), so functionality must be provided to address these events.
A variety of DHT strategies have been developed to manage the storage and retrieval of objects in a P2P system. FIG. 2 shows a Content Addressable Network (CAN) strategy, e.g., as described in S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, “A Scalable Content-Addressable Network,” ACM SigComm 2001, San Diego, Calif., USA, August 2001. This strategy models the DHT logical space as a D-dimensional Cartesian space 200. The CAN strategy partitions the space 200 as nodes join the DHT space 200. For instance, when node n1 joins, the CAN strategy allocates the entire space 200 to this node. When node n2 joins, the CAN strategy divides the space 200 into two halves and allocates each half to nodes n1 and n2, respectively. When node n3 joins, the CAN strategy divides the right half into upper and lower quarters, assigning the upper quarter to node n2 and the lower quarter to node n3. And when node n4 joins, the CAN strategy divides the lower right quarter into a left eighth (which is assigned to node n3) and a right eighth (which is assigned to node n4). This procedure is repeated as many times as necessary to dynamically account for nodes being adding and removed. The resultant partitions define logical spaces used to insert and retrieve objects into and from the distributed hash table. A node can be said to “own” the objects that map to its space.
FIG. 3 shows another strategy referred to as CHORD (e.g., as described in I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, “Chord: a Scalable Peer-To-Peer Lookup Service for Internet Applications,” ACM SigComm 2001, San Diego, Calif., USA, August 2001. In this strategy, the DHT logical space is structured as circular space 300. DHT nodes are assigned IDs and added to the circular DHT logical space 300 based of their assigned IDs. For instance, exemplary DHT nodes n1, n2, n3, n4, and n5 shown in FIG. 3 have assigned IDs that govern their “placement” on the circular DHT logical space 300. As in the case of FIG. 2, the DHT nodes partition the DHT logical space 300 as they are added, defining multiple subspaces or zones. These zones define the objects that each node “owns.” For instance, to insert an object into a distributed hash table that is governed by the DHT strategy shown in FIG. 3, the object is subjected to a hashing function to produce a key. The object is then stored at the DHT node have a zone assigned to that key (e.g., at the DHT node which encompasses a range of keys that include the object's key). In both the cases of FIG. 2 and FIG. 3, a variety of lookup strategies can be used to quickly find a particular node in the P2P system. In general, the lookup strategies involve making several “hops” in the DHT logical space to narrow in on the desired target DHT node. Various mechanisms are commonly provided to expedite this search. For instance, each DHT node in the CHORD strategy stores the IDs of a set of other DHT nodes. These other IDs can increase in exponential fashion, establishing so-called “fingers” that probe out into the logical space 300. This allows the lookup procedure to quickly locate a desired DHT node with a small number of hops.
FIGS. 2 and 3 provide merely a high level overview of two exemplary known DHT routing strategies. There are many other strategies. For instance, another popular routing strategy is the PASTRY routing strategy, as described in A. Rowstron and P. Druschel, “Pastry: Scalable, Distributed Object Location and Routing for Large-Scale Peer-To-Peer Systems,” 18th FIFP/ACM International Conference on Distributed Systems Platforms (Middleware), Heidelberg, Germany, November 2001.
P2P systems offer many benefits over conventional client-server strategies. For instance, P2P systems have the ability to automatically and freely expand and contract without central coordination. But this lack of supervisory coordination also poses various challenges. For instance, it may be desirable to have the P2P system act in concert to perform some global function. In various instances, it may be desirable to collect data from the participants of the P2P system. Or it may be desirable to disseminate information to the participants in the P2P system. With a client-server approach, a server can simply poll its clients to collect information from its clients, or broadcast information to its clients to disseminate information to its clients. But data gathering and dissemination becomes more problematic in a P2P system because it is formed by a loose alliance of interconnected peers that can freely come and go. Adding centralized conventional reporting functionality may have the effect of complicating the P2P system, and thus reducing its flexibility and utility.
There is accordingly an exemplary need in the art for an efficient strategy for interacting with a P2P DHT that will allow, for instance, for the gathering of data from its participants and the dissemination of information to its participants. Moreover, it is desirable to efficiently organize the P2P DHT and interact with it in operations that will profit from its efficiency, such in an application level multicasting operation.